package com.fulu.javabase.arithmetic;

import java.util.*;

public class LongestPalindrome {

    /**
     * budui
     * @param s
     * @return
     */
    public String longestPalindrome(String s){
        int length = s.length();
        byte[] arr = s.getBytes();
        // 保存最长的下标
        int[] idxes = new int[2];
        Map<Byte, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            Integer idx = map.get(arr[i]);
            if(idx == null){
                map.put(arr[i], i);
            }else{
                if(idxes[1] - idxes[0] < i + 1 - idx){
                    idxes[0] = idx;
                    idxes[1] = i + 1;
                }
            }
        }
        return s.substring(idxes[0], Math.max(idxes[1], 1));
    }

    /**
     * 应该用队列，X
      */
    public String longestPalindrome1(String s){
        Stack<Character> stack = new Stack<>();
        String result = "";
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if(stack.contains(c)){
                StringBuilder builder = new StringBuilder();
                builder.append(c);
                while(!stack.peek().equals(c)){
                    builder.append(stack.pop());
                }
                if(builder.length() + 1 > result.length()){
                    result = builder.append(c).reverse().toString();
                }
            }
            stack.push(s.charAt(i));
        }

        return result;
    }

    /**
     * 超时
     * @param s
     * @return
     */
    public String longestPalindrome2(String s){
        int length = s.length();
        if(length == 1) {
            return s;
        }
        if(length == 2){
            return s.charAt(0) == s.charAt(1) ? s : s.substring(0, 1);
        }

        for (int i = length; i > 1; i--) {
            int pre = 0;
            for (int j = i; j <= length; j++) {
                String subs = s.substring(pre, j);

                String s1 = subs.substring(0, subs.length() / 2);
                String s2 = subs.substring(subs.length() % 2 == 1 ? subs.length() / 2 + 1 : subs.length() / 2);
                StringBuilder builder = new StringBuilder(s2);
                if(builder.reverse().toString().contains(s1)){
                    return subs;
                }
                pre++;
            }
        }

        return s.substring(0, 1);
    }
    public String longestPalindrome3(String s){
        return null;
    }

    public static void main(String[] args) {
        String s = "abcda";
        String result = new LongestPalindrome().longestPalindrome2(s);
        System.out.println(result);
    }
}
